/**
 * @name   LinkedList.c
 * @brief  这是单向链表的代码案例，学习单向链表的结点的增删改查
 * @date   2024/12/24
 * @anchor boluzs@163.com
 * @note
 *
 * @version 0.0.1
 *
 * 版权声明
 * CopyRight (c)   2019-2024   boluzs@163.com    All Right Reciver
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>

typedef int DataType_t; // 数据域中的数据类型，为了提高程序的可移植性

typedef struct Node
{
    DataType_t Data;   // 数据域，用于存放当前结点的数据
    struct Node *Next; // 指针域，用于记录下个结点的地址
} Node_t, *Node_p;

/**
 * @name: LinkedList_Create
 * @brief: 创建带有头结点的空链表
 * @note: 单向链表是具有头结点，头结点类型和其他结点类型一致，但是头结点不存储有效数据
 * @retval: 函数调用成功，返回Node_p类型指针
 */
Node_p LinkedList_Create(void)
{
    // 1.为头结点申请堆内存，并进行错误处理
    Node_p Pmanager = (Node_p)calloc(1, sizeof(Node_t));
    if (NULL == Pmanager)
    {
        fprintf(stderr, "Calloc For Node Error,errno=%d,%s\n", errno, strerror(errno));
        exit(-1);
    }

    // 2.初始化头结点指针域（数据域是空闲的）
    Pmanager->Next = NULL;
    printf("Create LinkedList Successfully!\n");
    return Pmanager;
}

/**
 * @name: LinkedList_NewNode
 * @brief: 创建新结点
 * @param {DataType_t} Data：待创建的结点数据域数据
 * @note: 新结点没有插入链表中，所以新结点指针域初值为NULL
 * @retval: 函数调用成功，返回Node_p类型指针
 */
Node_p LinkedList_NewNode(DataType_t Data)
{
    // 1.为新结点申请堆内存，并进行错误处理
    Node_p NewNode = (Node_p)calloc(1, sizeof(Node_t));
    if (NULL == NewNode)
    {
        fprintf(stderr, "Calloc For Node Error,errno=%d,%s\n", errno, strerror(errno));
        exit(-1);
    }
    // 2.初始化新结点
    NewNode->Data = Data;
    NewNode->Next = NULL;
    printf("Create NewNode Successfully!\n");
    return NewNode;
}

/**
 * @name: LinkedList_HeadInsert
 * @brief: 利用头插法实现结点插入
 * @param {Node_p} HeadPointer：指的是指向头结点的头指针
 * @param {DataType_t} Data：指的是待插入结点的数据域的值
 * @note: 头插法指的是把新结点作为链表的首结点
 * @retval: 成功返回true，失败返回false
 */
bool LinkedList_HeadInsert(Node_p HeadPointer, DataType_t Data)
{
    // 为了提高程序的可靠性，所以需要对头指针进行备份
    Node_p p = HeadPointer;

    // 1.校验参数有效性
    if (NULL == HeadPointer)
    {
        fprintf(stderr, "Insert Error,Argument Invaild\n");
        return false;
    }

    // 2.创建新结点
    Node_p NewNode = LinkedList_NewNode(Data);

    // 3.判断链表是否为空
    if (NULL == p->Next)
    {
        // 4.链表为空的情况
        p->Next = NewNode;
    }
    else
    {
        // 5.链表不为空的情况
        NewNode->Next = p->Next;
        p->Next = NewNode;
    }
    return true;
}

/**
 * @name: LinkedList_TailInsert
 * @brief: 利用尾插法实现结点插入
 * @param {Node_p} HeadPointer：指的是指向头结点的头指针
 * @param {DataType_t} Data：指的是待插入结点的数据域的值
 * @note: 尾插法指的是把新结点作为链表的尾结点
 * @retval: 成功返回true，失败返回false
 */
bool LinkedList_TailInsert(Node_p HeadPointer, DataType_t Data)
{
    // 为了提高程序的可靠性，所以需要对头指针进行备份
    Node_p p = HeadPointer;

    // 1.校验参数有效性
    if (NULL == HeadPointer)
    {
        fprintf(stderr, "Insert Error,Argument Invaild\n");
        return false;
    }

    // 2.创建新结点
    Node_p NewNode = LinkedList_NewNode(Data);

    // 3.遍历找尾结点
    while (NULL != p->Next)
    {
        p = p->Next;
    }
    p->Next = NewNode;
    return true;
}

/**
 * @name: LinkedList_HeadDel
 * @brief: 实现头删法
 * @param {Node_p} HeadPointer：指的是指向头结点的头指针
 * @note: None
 * @retval: 成功返回true，失败返回false
 */
bool LinkedList_HeadDel(Node_p HeadPointer)
{
    // 为了提高程序的可靠性，所以需要对头指针进行备份
    Node_p p = HeadPointer;

    // 1.校验参数有效性
    if (NULL == HeadPointer)
    {
        fprintf(stderr, "Delete Error,Argument Invaild\n");
        return false;
    }

    // 2.判断链表是否为空
    if (p->Next == NULL)
    {
        fprintf(stderr, "Delete Error,LinkedList Is Empty\n");
        return false;
    }

    // 备份->链接->断开->释放
    // 3.提前备份首结点地址
    Node_p DelNode = p->Next;
    // 4.让头结点的指针域指向首结点的直接后继结点
    p->Next = p->Next->Next;
    // 5.让首结点的指针域指向NULL
    DelNode->Next = NULL;
    // 6.释放待删除的结点空间
    free(DelNode);
    return true;
}

/**
 * @name: LinkedList_TailDel
 * @brief: 实现尾删法
 * @param {Node_p} HeadPointer：指的是指向头结点的头指针
 * @note: None
 * @retval: 成功返回true，失败返回false
 */
bool LinkedList_TailDel(Node_p HeadPointer)
{
    // 为了提高程序的可靠性，所以需要对头结点进行备份
    Node_p p_prev = HeadPointer;

    // 为了提高程序的可靠性，所以需要对首结点进行备份
    Node_p p_current = p_prev->Next;

    // 1.校验参数有效性
    if (NULL == HeadPointer)
    {
        fprintf(stderr, "Delete Error,Argument Invaild\n");
        return false;
    }

    // 2.判断链表是否为空
    if (p_current == NULL)
    {
        fprintf(stderr, "Delete Error,LinkedList Is Empty\n");
        return false;
    }

    // 3.对单向链表进行遍历，找到尾结点和尾结点的直接前驱
    while (NULL != p_current->Next)
    {
        p_prev = p_prev->Next;
        p_current = p_current->Next;
    }

    // 4.断开尾结点的直接前驱和尾结点的链接
    p_prev->Next = NULL;

    // 5.释放尾结点
    free(p_current);
    return true;
}

/**
 * @name: LinkedList_SelectKData
 * @brief: 实现查找倒数第K个结点的Data
 * @param {Node_p} HeadPointer：指的是指向头结点的头指针
 * @note: None
 * @retval: 成功返回1，失败返回0
 */
int LinkedList_SelectKData(Node_p HeadPointer, int k)
{
    // 为了提高程序的可靠性，所以需要对头指针进行备份
    Node_p p = HeadPointer;

    // 1.校验参数有效性
    if (NULL == HeadPointer)
    {
        fprintf(stderr, "Select Error,Argument Invaild\n");
        return false;
    }

    // 2.判断链表是否为空
    if (p->Next == NULL)
    {
        fprintf(stderr, "Select Error,LinkedList Is Empty\n");
        return false;
    }

    // 3.提前备份首结点地址
    Node_p temp = p;

    // 4.记录移动次数
    int cnt = 1;

    // 5.对单向链表进行遍历
    while (NULL != p->Next)
    {
        p = p->Next;
        cnt++;
        // 6.当p走到倒数第k个结点后，temp才开始移动
        if (cnt > k)
        {
            temp = temp->Next;
        }
    }

    // 7.如果temp==head，证明结点数量不够
    if (temp == HeadPointer)
    {
        return 0;
    }

    printf("当前链表倒数第%d个结点值是：%d\n", k, temp->Data);
    return 1;
}

/**
 * @name: LinkedList_Print
 * @brief: 打印链表
 * @param {Node_p} HeadPointer：指的是指向头结点的头指针
 * @note: None
 * @retval: 成功返回true，失败返回false
 */
bool LinkedList_Print(Node_p HeadPointer)
{

    // 1.备份
    Node_p p = HeadPointer;

    // 1.校验参数有效性
    if (NULL == HeadPointer)
    {
        fprintf(stderr, "Print Error,Argument Invaild\n");
        return false;
    }

    // 2.判断链表是否为空
    if (p->Next == NULL)
    {
        fprintf(stderr, "Print Error,LinkedList Is Empty\n");
        return false;
    }
    printf("当前链表为：");
    // 2.遍历
    while (p->Next != NULL)
    {
        p = p->Next;
        printf("%d ", p->Data);
    }
    printf("\n");
    return true;
}

/**
 * @name: LinkedList_DelMinNode
 * @brief: 删除链表最小值结点
 * @param {Node_p} HeadPointer：指的是指向头结点的头指针
 * @note: None
 * @retval: 成功返回true，失败返回false
 */
bool LinkedList_DelMinNode(Node_p HeadPointer)
{

    // 1.备份
    Node_p P = HeadPointer->Next;    // 用于记录当前结点
    Node_p Ptemp = HeadPointer;      // 用于记录当前结点的前驱结点
    Node_p Pmin = HeadPointer->Next; // 用于记录最小结点
    Node_p Pmin_temp = HeadPointer;  // 用于记录最小结点的前驱结点

    // 2.校验参数有效性
    if (NULL == HeadPointer)
    {
        fprintf(stderr, "Delete Error,Argument Invaild\n");
        return false;
    }

    // 3.判断链表是否为空
    if (Ptemp->Next == NULL)
    {
        fprintf(stderr, "Delete Error,LinkedList Is Empty\n");
        return false;
    }
    // 4.遍历
    while (P != NULL)
    {
        // 5.跟最小的结点比较，比Pmin小则存储到Pmin中
        if (P->Data < Pmin->Data)
        {
            Pmin = P;
            Pmin_temp = Ptemp;
        }
        // 6.P和Ptemp继续移动
        P = P->Next;
        Ptemp = Ptemp->Next;
    }
    // 7.将Pmin_temp的指针域指向Pmin的指针域
    Pmin_temp->Next = Pmin->Next;
    Pmin->Next = NULL;
    free(Pmin);
    return true;
}

/**************************************************************************
 * @name: LinkedList_ToSet
 * @brief: 递增非空单链表去重
 * @param {Node_p} HeadPointer：指的是指向头结点的头指针
 * @note: None
 * @retval: 成功返回true，失败返回false
 **************************************************************************/
bool LinkedList_ToSet(Node_p HeadPointer)
{
    // 1.用于记录是否有重复值域的结点
    Node_p p = HeadPointer->Next;
    // 2.用于记录需要删除的结点
    Node_p temp = HeadPointer->Next;

    // 3.遍历p是否等于temp
    while (p == temp)
    {
        // 4.相等则将temp往后移
        temp = temp->Next;
        // 5.比较p和temp的数据域是否相等
        while (temp->Data == p->Data)
        {
            // 6.判断temp是否尾结点
            if (temp->Next == NULL)
            {
                p->Next = NULL;
                free(temp);
            }
            else
            {
                // 7.删除temp结点
                p->Next = temp->Next;
                temp->Next = NULL;
                free(temp);
                // 8.将temp结点往后移动
                temp = p->Next;
            }
        }
        // 9.上面的循环跳出，则证明temp的结点的数据域不等于p的数据域，并且p不是尾结点，所以将p往后移动
        if (p->Next != NULL)
        {
            p = p->Next;
        }
    }
    return true;
}

int main(int argc, char const *argv[])
{
    // 1.创建链表
    Node_p Linked_List = LinkedList_Create();

    // 2.头插法插入结点
    // LinkedList_HeadInsert(Linked_List, 2);
    // LinkedList_HeadInsert(Linked_List, 5);
    // LinkedList_HeadInsert(Linked_List, 1);
    // LinkedList_HeadInsert(Linked_List, 4);
    // LinkedList_HeadInsert(Linked_List, 6);
    // LinkedList_Print(Linked_List);

    // 3.尾插法插入结点
    LinkedList_TailInsert(Linked_List, 1);
    LinkedList_TailInsert(Linked_List, 1);
    LinkedList_TailInsert(Linked_List, 2);
    LinkedList_TailInsert(Linked_List, 3);
    LinkedList_TailInsert(Linked_List, 3);
    LinkedList_TailInsert(Linked_List, 3);
    LinkedList_TailInsert(Linked_List, 4);
    LinkedList_TailInsert(Linked_List, 4);
    LinkedList_TailInsert(Linked_List, 7);
    LinkedList_TailInsert(Linked_List, 7);
    LinkedList_TailInsert(Linked_List, 7);
    LinkedList_TailInsert(Linked_List, 9);
    LinkedList_TailInsert(Linked_List, 9);
    LinkedList_TailInsert(Linked_List, 9);
    LinkedList_Print(Linked_List);

    // 4.头删法删除结点
    // LinkedList_HeadDel(Linked_List);
    // printf("执行了一次头删法删除结点\n");
    // LinkedList_Print(Linked_List);

    // 5.尾删法删除结点
    // LinkedList_TailDel(Linked_List);
    // printf("执行了一次尾删法删除结点\n");
    // LinkedList_Print(Linked_List);

    // 6.查找倒数第K个结点值
    // LinkedList_SelectKData(Linked_List, 1);

    // 7.删除链表最小值结点
    // LinkedList_DelMinNode(Linked_List);
    // printf("执行了一次删除链表最小值结点\n");
    // LinkedList_Print(Linked_List);
    // LinkedList_DelMinNode(Linked_List);
    // printf("执行了一次删除链表最小值结点\n");
    // LinkedList_Print(Linked_List);

    LinkedList_ToSet(Linked_List);
    LinkedList_Print(Linked_List);

    return 0;
}
